package likou.offer2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/09/22 16:10
 */
public class _086 {
    public static void main(String[] args) {
        _086 one = new _086();
        one.partition("abbab");
    }

    List<String[]> list = new ArrayList<>();

    public String[][] partition(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        int[][] nums = new int[n][n + 1];
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(cs[i]);
            nums[i][1] = i + 1;
            nums[i][0]++;
            for (int j = i + 1; j < n; j++) {
                sb.append(cs[j]);
                if (cs[i] == cs[j] && new StringBuilder(sb).reverse().toString().equals(sb.toString())) {
                    nums[i][0]++;
                    nums[i][nums[i][0]] = i + sb.length();
                }
            }
        }
        for (int[] str : nums) {
            System.out.println(Arrays.toString(str));
        }
        dfs(s, new ArrayList<>(), 0, nums);

        String[][] strings = list.toArray(new String[list.size()][]);
        for (String[] str : strings) {
            System.out.println(Arrays.toString(str));
        }
        return strings;
    }

    public void dfs(String str, List<String> res, int start, int[][] nums) {
        if (start == str.length()) {
            list.add(res.toArray(new String[res.size()]));
            return;
        }
        for (int i = 1; i <= nums[start][0]; i++) {
            res.add(str.substring(start, nums[start][i]));
            dfs(str, res, nums[start][i], nums);
            res.remove(res.size() - 1);
        }
    }
}
